// ml:run = time -p $bin < input
// ml:opt = 0
// ml:ccf += -g
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int n, m, s, N;
int g[150][150];
int degree[150];
int ans;
int rec[1050];
long long g1[1050], g2[1050];
int li[1050];
int edge[2050][2], used[2050];
int suffix[150][150];

void dfs(int flor, int last, ll now1, ll now2){
    if(flor==s){
        //for(int i=1;i<=s;i++)printf("%d%c", rec[i], i==s?'\n':' ');
        ans++;return;
    }
    if (N-last<s-flor) return;
    int M=N;
    for(int i=1;i<=flor;i++){
        for(int j=N;li[j]>rec[i];j--){
            if(suffix[i][j]==s-flor){
                M=min(M, j);
            }
        }
    }
    for(int j=last+1;j<=M;j++){
        int i=li[j];
        ll tmp1=now1 & g1[i], tmp2=now2 & g2[i];
        if(tmp1==now1 && tmp2==now2){
            rec[flor+1]=i;
            if (i<=50)
                dfs(flor+1, j, now1|(1LL<<i), now2);
            else
                dfs(flor+1, j, now1, now2|(1LL<<(i-50)));
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        N=0;
        scanf("%d%d%d", &n, &m, &s);
        memset(used, 0, sizeof(used));
        memset(g, 0, sizeof(g));
        memset(degree, 0, sizeof(degree));
        memset(g1, 0, sizeof(g1));
        memset(g2, 0, sizeof(g2));
        for(int i=1;i<=m;i++){
            int x, y;
            scanf("%d%d", &x, &y);
            edge[i][0]=x;edge[i][1]=y;
            degree[x]++;
            degree[y]++;
            g[x][y]=g[y][x]=1;
            if (x<=50)
                g1[y] = g1[y]|(1LL<<x);
            else g2[y] = g2[y]|(1LL<<(x-50));
            if (y<=50)
                g1[x] = g1[x]|(1LL<<y);
            else g2[x] = g2[x]|(1LL<<(y-50));
        }
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                if (!used[j] && (degree[edge[j][0]]<s-1 || degree[edge[j][1]]<s-1)){
                    degree[edge[j][0]]--;
                    degree[edge[j][1]]--;
                    g[edge[j][0]][edge[j][1]]=g[edge[j][1]][edge[j][0]]=0;
                    used[j]=1;
                }
        for (int i=1;i<=n;i++)
            if (degree[i]>=s-1){
                li[++N]=i;
            }
        memset(suffix, 0, sizeof(suffix));
        for(int i=1;i<=N;i++){
            for(int j=N;j>=1;j--){
                suffix[li[i]][li[j]]=g[li[i]][li[j]];
                if(j!=N)suffix[li[i]][li[j]]+=suffix[li[i]][li[j+1]];
            }
        }


        ans=0;
        dfs(0, 0, 0, 0);
        printf("%d\n", ans);
    }
}

